

/*-------------------------------------------------------------------------
 *
 * dynahash.c
 *	  动态链式哈希表
 *
 * dynahash.c 支持本地到后端的哈希表和共享内存中的哈希表。
 * 对于共享哈希表，调用者有责任提供适当的访问互锁。最简单的约定是
 * 一个 LWLock 保护整个哈希表。搜索（HASH_FIND 或 hash_seq_search）只需要共享锁，但任何更新都需要独占锁。
 * 对于使用频繁的共享表，单锁方法会产生并发瓶颈，因此我们还支持“分区”锁，
 * 在这种模式下，有多个 LWLocks 保护表的不同子集。要在分区模式下使用哈希表，
 * 必须将 HASH_PARTITION 标志传递给 hash_create。这防止在运行时分裂桶。
 * 因此，每个哈希桶链独立操作，初始化后哈希头的其他字段不会变化，除了 nentries 和 freeList。
 * （分区表使用这些字段的多个副本，由自旋锁保护，以提高并发性。）
 * 这允许将任何哈希桶子集视为单独的可锁分区。我们希望调用者将查找键的哈希值的低位
 * 作为分区号——这将有效，因为 calc_bucket() 将哈希值映射到桶号的方式。
 *
 * 对于共享内存中的哈希表，内存分配函数应该符合 malloc 失败时返回 NULL 的语义。
 * 对于本地内存中的哈希表，我们通常使用 palloc()，失败时会抛出错误。
 * 本文件中的代码必须处理这两种情况。
 *
 * dynahash.c 为以下类型的查找键提供支持：
 *
 * 1. 以 NULL 结尾的 C 字符串（必要时截断以适应键大小），
 * 比较方式类似于 strcmp()。通过在 hash_create 中指定 HASH_STRINGS 标志选择此方式。
 *
 * 2. 大小为 keysize 的任意二进制数据，比较方式类似于 memcmp()。
 * （调用者必须确保键中没有未定义的填充位！）
 * 通过在 hash_create 中指定 HASH_BLOBS 标志选择此方式。
 *
 * 3. 可以通过指定用户提供的哈希、比较和/或键复制函数来选择更复杂的键行为。
 * 至少必须提供一个哈希函数；当选择用户定义的哈希函数时，比较默认为 memcmp()，键复制默认为 memcpy()。
 *
 * 与 simplehash 相比，dynahash 具有以下优点：
 *
 * - 支持分区，这对于使用锁的共享内存访问非常有用。
 * - 共享内存哈希在启动时在固定大小区域内分配，并可以通过名称从其他进程发现。
 * - 因为在哈希冲突情况下不需要移动条目，dynahash 对于大条目具有更好的性能。
 * - 保证指向条目的稳定指针。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/hash/dynahash.c
 *
 *-------------------------------------------------------------------------
 */


/*
 * 原始注释：
 *
 * 动态哈希，参考CACM 1988年4月第446-457页，Per-Ake Larson所著。
 * 用C语言编写，进行了小幅代码改进，并使用hsearch(3)接口，
 * 作者为ejp@ausmelb.oz，日期：1988年7月26日：13:16；
 * 此外，添加了hcreate/hdestroy例程以模拟hsearch(3)。
 *
 * 这些例程模拟hsearch(3)及其相关函数，重要的不同点在于哈希表是动态的——可以无限制地 
 * 增长超出其原始大小（由hcreate()提供）。
 *
 * 性能似乎与hsearch(3)相当。
 * hsearch(3)的'man'页面中提到的“源代码”选项未实现；否则功能是相同的。
 *
 * 编译控制：
 * HASH_DEBUG控制一些信息跟踪，主要用于调试。
 * HASH_STATISTICS会维护HashAccesses和HashCollisions；
 * 当与HASH_DEBUG结合使用时，这些会通过hdestroy()显示。
 *
 * 如有问题请联系ejp@ausmelb.oz。警告：依赖于预处理器
 * 连接特性，在可能不必要的代码“优化”中。
 *
 * 1990年2月，margo@postgres.berkeley.edu修改
 * 		添加了多表接口
 * 1990年4月，sullivan@postgres.berkeley.edu修改
 * 		更改了共享内存的ctl结构
 */

#include "postgres.h"

#include <limits.h>

#include "access/xact.h"
#include "common/hashfn.h"
#include "port/pg_bitutils.h"
#include "storage/shmem.h"
#include "storage/spin.h"
#include "utils/dynahash.h"
#include "utils/memutils.h"


/*
 * 常量
 *
 * 哈希表具有一个顶级“目录”，其每个条目指向一个“段”，
 * 每个段包含ssize个桶头。哈希桶的最大数量因此为
 * dsize * ssize（但dsize可能是可扩展的）。当然，
 * 表中的记录数量可以更大，但我们不希望每个桶中有过多
 * 记录，否则性能会下降。
 *
 * 在分配于共享内存的哈希表中，目录不能扩展，
 * 因为它必须保持在固定地址。目录大小
 * 应该使用hash_select_dirsize来选择（而且你最好对
 * 最大条目数量有个大致了解！）。对于非共享哈希
 * 表，初始目录大小可以保持在默认值。
 */
#define DEF_SEGSIZE			   256
#define DEF_SEGSIZE_SHIFT	   8	/* 必须为log2(DEF_SEGSIZE) */
#define DEF_DIRSIZE			   256

/* 用于分区哈希表的自由链表数量。 */
#define NUM_FREELISTS			32

/* 哈希桶是一个 HASHELEMENT 的链表 */
typedef HASHELEMENT *HASHBUCKET;

/* 哈希段是桶头的数组 */
typedef HASHBUCKET *HASHSEGMENT;

/*
 * 每个闲置列表的数据。
 *
 * 在分区哈希表中，每个闲置列表与一组特定的哈希码相关联，
 * 由下面的 FREELIST_IDX() 宏确定。
 * nentries 跟踪具有这些哈希码的活动哈希表条目的数量
 * （并不是闲置列表中的条目数量，正如你可能期望的那样）。
 *
 * 闲置列表的覆盖范围可能多于或少于一个分区，因此
 * 它需要自己的锁，而不是依赖调用者的锁定。依赖于这一点
 * 即使覆盖相同也不行，因为偶尔需要从另一个闲置列表中“借用”条目；见 get_hash_entry()。
 *
 * 使用 FreeListData 数组而不是单独的互斥数组、nentries 和 freeLists 可以帮助减少
 * 不同互斥体之间的缓存行共享。
 */
typedef struct
{
	slock_t		mutex;			/* 该闲置列表的自旋锁 */
	long		nentries;		/* 关联桶中的条目数量 */
	HASHELEMENT *freeList;		/* 空闲元素的链 */
} FreeListData;

/*
 * 哈希表的头部结构 --- 包含所有可变信息
 *
 * 在共享内存哈希表中，HASHHDR 位于共享内存中，而
 * 每个后端都有一个本地的 HTAB 结构。对于非共享表，
 * HASHHDR 和 HTAB 之间没有任何功能上的区别，但我们仍然将它们分开，
 * 以便在共享和非共享表之间共享代码。
 */
struct HASHHDR
{
	/*
	 * 闲置列表可能成为高并发哈希表中的争用点，
	 * 所以我们使用一个闲置列表数组，每个都有自己的互斥体和
	 * nentries 计数，而不仅仅是一个。尽管闲置列表
	 * 通常独立操作，但在必要时我们将从
	 * 哈希码的默认闲置列表以外的闲置列表中回收条目。
	 *
	 * 如果哈希表没有分区，则只使用 freeList[0]，
	 * 其自旋锁根本不使用；调用者的锁定被认为是足够的。
	 */
	FreeListData freeList[NUM_FREELISTS];

	/* 这些字段可以更改，但在分区表中不可更改 */
	/* 此外，即使在非分区的共享表中，dsize 也不能更改 */
	long		dsize;			/* 目录大小 */
	long		nsegs;			/* 分配的段数（<= dsize） */
	uint32		max_bucket;		/* 使用中的最大桶的 ID */
	uint32		high_mask;		/* 用于对整个表取模的掩码 */
	uint32		low_mask;		/* 用于对表的下半部分取模的掩码 */

	/* 这些字段在哈希表创建时固定 */
	Size		keysize;		/* 哈希键的字节长度 */
	Size		entrysize;		/* 用户元素的总大小（以字节为单位） */
	long		num_partitions; /* 分区数量（必须是 2 的幂），或 0 */
	long		max_dsize;		/* 如果目录是固定大小，'dsize' 限制 */
	long		ssize;			/* 段大小 --- 必须是 2 的幂 */
	int			sshift;			/* 段偏移 = log2(ssize) */
	int			nelem_alloc;	/* 一次分配的条目数量 */

#ifdef HASH_STATISTICS

	/*
	 * 在这里计数统计信息。注意：统计代码不考虑互斥体，
	 * 所以在分区表中计数可能会有些被损坏。
	 */
	long		accesses;
	long		collisions;
#endif
};

#define IS_PARTITIONED(hctl)  ((hctl)->num_partitions != 0)

#define FREELIST_IDX(hctl, hashcode) \
	(IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0)

/*
 * 哈希表的顶级控制结构 --- 在共享表中，每个后端
 * 都有自己的副本（因为在运行时没有字段会改变）
 */
struct HTAB
{
	HASHHDR    *hctl;			/* => 共享控制信息 */
	HASHSEGMENT *dir;			/* 段起始位置的目录 */
	HashValueFunc hash;			/* 哈希函数 */
	HashCompareFunc match;		/* 键比较函数 */
	HashCopyFunc keycopy;		/* 键复制函数 */
	HashAllocFunc alloc;		/* 内存分配器 */
	MemoryContext hcxt;			/* 如果使用默认分配器则为内存上下文 */
	char	   *tabname;		/* 表名（用于错误信息） */
	bool		isshared;		/* 如果表在共享内存中则为真 */
	bool		isfixed;		/* 如果为真，则不扩大 */

	/* 冻结共享表是不被允许的，因此我们可以在此保持状态 */
	bool		frozen;			/* true = 不再允许插入 */

	/* 我们保留这些固定值的本地副本以减少竞争 */
	Size		keysize;		/* 哈希键的字节长度 */
	long		ssize;			/* 段大小 --- 必须是 2 的幂 */
	int			sshift;			/* 段偏移 = log2(ssize) */
};

/* 
 * HASHELEMENT 的键（也称为条目）部分
 */
#define ELEMENTKEY(helem)  (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))

/* 
 * 给定键的指针获取元素指针
 */
#define ELEMENT_FROM_KEY(key)  \
	((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))

/* 
 * 快速 MOD 算术，假设 y 是 2 的幂！
 */
#define MOD(x,y)			   ((x) & ((y)-1))

#ifdef HASH_STATISTICS
static long hash_accesses,
			hash_collisions,
			hash_expansions;
#endif

/* 
 * 私有函数原型
 */
static void *fc_DynaHashAlloc(Size fc_size);
static HASHSEGMENT fc_seg_alloc(HTAB *fc_hashp);
static bool fc_element_alloc(HTAB *fc_hashp, int fc_nelem, int fc_freelist_idx);
static bool fc_dir_realloc(HTAB *fc_hashp);
static bool fc_expand_table(HTAB *fc_hashp);
static HASHBUCKET get_hash_entry(HTAB *fc_hashp, int fc_freelist_idx);
static void fc_hdefault(HTAB *fc_hashp);
static int	fc_choose_nelem_alloc(Size fc_entrysize);
static bool fc_init_htab(HTAB *fc_hashp, long fc_nelem);
static void fc_hash_corrupted(HTAB *fc_hashp);
static long fc_next_pow2_long(long fc_num);
static int	fc_next_pow2_int(long fc_num);
static void fc_register_seq_scan(HTAB *fc_hashp);
static void fc_deregister_seq_scan(HTAB *fc_hashp);
static bool fc_has_seq_scans(HTAB *fc_hashp);


/* 
 * 内存分配支持
 */
static MemoryContext CurrentDynaHashCxt = NULL;

static void * fc_DynaHashAlloc(Size fc_size)
{
	Assert(MemoryContextIsValid(CurrentDynaHashCxt));
	return MemoryContextAlloc(CurrentDynaHashCxt, fc_size);
}


/* 
 * 适用于字符串键的 HashCompareFunc
 * 
 * 由于我们使用 strlcpy() 复制键，因此它们将在 keysize-1 字节处被截断，
 * 因此我们只能比较这么多……因此 strncmp 几乎但不完全是正确的。
 */
static int fc_string_compare(const char *fc_key1, const char *fc_key2, Size fc_keysize)
{
	return strncmp(fc_key1, fc_key2, fc_keysize - 1);
}


/************************** 创建例程 **********************/

/* 
 * hash_create -- 创建一个新的动态哈希表
 * 
 *	tabname：表的名称（用于调试目的）
 *	nelem：预期的最大元素数量
 *	*info：附加的表参数，如标志所示
 *	flags：指示要从 *info 获取哪些参数的位掩码
 * 
 * flags 值 *必需* 包含 HASH_ELEM。（之前，这在名义上是可选的，
 * 但默认的 keysize 和 entrysize 值是无用的。）
 * flags 值还必须包含 HASH_STRINGS、HASH_BLOBS 或 HASH_FUNCTION 之一，
 * 以定义键哈希语义（C 字符串、二进制大对象或自定义，分别）。提供自定义
 * 哈希函数的调用者可能还希望使用 HASH_COMPARE，可能还希望使用 
 * HASH_KEYCOPY，以控制键比较和复制。
 * 另一个常用标志是 HASH_CONTEXT，以在 info->hcxt 下分配哈希表
 * 而不是在 TopMemoryContext 下；默认行为仅适用于会话生命周期的哈希表。
 * 其他标志位是特殊用途的，除与共享内存哈希表相关的位外，通常不使用，
 * 有关共享内存哈希表，请参见 ShmemInitHash()。
 * 
 * 当关联的标志位设置时，*info 中的字段为只读。
 * 不需要初始化 *info 的其他字段。
 * tabname 或 *info 在 hash_create() 调用后不需要保持。
 * 
 * 注意：hash_create() 的调用者显式指定 string_hash、tag_hash、uint32_hash 或 oid_hash 是不推荐的。
 * 只需设置 HASH_STRINGS 或 HASH_BLOBS。仅当您想要的内容与这些不同时使用 HASH_FUNCTION。
 * 
 * 注意：对于共享内存哈希表，nelem 需要是一个非常好的估算，因为我们不能动态扩展表。
 * 但是，未共享的哈希表可以动态扩展，因此 nelem 较小更好，如果超过了让表增长。过大的 nelem 会影响 
 * hash_seq_search 的速度而不会带来太多好处。
 */
HTAB * hash_create(const char *fc_tabname, long fc_nelem, const HASHCTL *fc_info, int fc_flags)
{
	HTAB	   *fc_hashp;
	HASHHDR    *fc_hctl;

	/* 
 * 哈希表现在为键和数据分配空间，但您必须说明
 * 分配多少空间。
 */
	Assert(fc_flags & HASH_ELEM);
	Assert(fc_info->keysize > 0);
	Assert(fc_info->entrysize >= fc_info->keysize);

	/* 
 * 对于共享哈希表，我们有一个本地哈希头（HTAB 结构），
 * 我们在 TopMemoryContext 中分配；所有其他内容都在共享内存中。
 * 
 * 对于非共享哈希表，包括哈希头的所有内容都在
 * 特别为哈希表创建的内存上下文中---这使得
 * hash_destroy 非常简单。内存上下文成为案例定义的 
 * 上下文的子项，或者如果没有指定，则为 TopMemoryContext。
 */
	if (fc_flags & HASH_SHARED_MEM)
	{
		/* 设置以分配哈希头 */
		CurrentDynaHashCxt = TopMemoryContext;
	}
	else
	{
		/* 创建哈希表的私有内存上下文 */
		if (fc_flags & HASH_CONTEXT)
			CurrentDynaHashCxt = fc_info->hcxt;
		else
			CurrentDynaHashCxt = TopMemoryContext;
		CurrentDynaHashCxt = AllocSetContextCreate(CurrentDynaHashCxt,
												   "dynahash",
												   ALLOCSET_DEFAULT_SIZES);
	}

	/* 初始化哈希头，加上表名的副本 */
	fc_hashp = (HTAB *) fc_DynaHashAlloc(sizeof(HTAB) + strlen(fc_tabname) + 1);
	MemSet(fc_hashp, 0, sizeof(HTAB));

	fc_hashp->tabname = (char *) (fc_hashp + 1);
	strcpy(fc_hashp->tabname, fc_tabname);

	/* 如果我们有私有上下文，则用哈希表的名称标记它 */
	if (!(fc_flags & HASH_SHARED_MEM))
		MemoryContextSetIdentifier(CurrentDynaHashCxt, fc_hashp->tabname);

	/* 
 * 选择适当的哈希函数（请参见文件开头的注释）。
 */
	if (fc_flags & HASH_FUNCTION)
	{
		Assert(!(fc_flags & (HASH_BLOBS | HASH_STRINGS)));
		fc_hashp->hash = fc_info->hash;
	}
	else if (fc_flags & HASH_BLOBS)
	{
		Assert(!(fc_flags & HASH_STRINGS));
		/* 我们可以针对常见的键大小优化哈希 */
		if (fc_info->keysize == sizeof(uint32))
			fc_hashp->hash = uint32_hash;
		else
			fc_hashp->hash = tag_hash;
	}
	else
	{
		/* 
 * string_hash 曾被认为是默认哈希方法，在非断言构建中它实际上仍然是。
 * 但我们现在认为不明确声明 HASH_STRINGS 是一个断言错误。为帮助
 * 捕获错误使用 HASH_STRINGS，我们还要求有一个相当长的字符串长度：如果键大小仅为 4 或 8 字节，
 * 那几乎肯定是整数或指针，而不是字符串。
 */
		Assert(fc_flags & HASH_STRINGS);
		Assert(fc_info->keysize > 8);

		fc_hashp->hash = string_hash;
	}

	/* 
 * 如果您不指定匹配函数，则在使用 string_hash 时默认为 string_compare，
 * 否则默认为 memcmp。
 * 
 * 注意：显式指定 string_hash 是不推荐的，因为在某些平台上
 * 这可能不适用于可加载模块的调用者，因为这会引用弹簧，而不是 string_hash 函数本身。
 * 请改用 HASH_STRINGS。
 */
	if (fc_flags & HASH_COMPARE)
		fc_hashp->match = fc_info->match;
	else if (fc_hashp->hash == string_hash)
		fc_hashp->match = (HashCompareFunc) fc_string_compare;
	else
		fc_hashp->match = memcmp;

	/*
	 * 类似地，键复制函数默认为strlcpy或memcpy。
	 */
	if (fc_flags & HASH_KEYCOPY)
		fc_hashp->keycopy = fc_info->keycopy;
	else if (fc_hashp->hash == string_hash)
	{
		/*
		 * keycopy的签名是为了memcpy()，它返回
		 * void*，但strlcpy()返回size_t。由于我们从不使用keycopy的返回
		 * 值，并且size_t几乎总是与void *相同的大小，这应该是安全的。中间的额外强制转换是为了
		 * 避免-Wcast-function-type的警告。
		 */
		fc_hashp->keycopy = (HashCopyFunc) (pg_funcptr_t) strlcpy;
	}
	else
		fc_hashp->keycopy = memcpy;

	/* 还选择条目分配函数。 */
	if (fc_flags & HASH_ALLOC)
		fc_hashp->alloc = fc_info->alloc;
	else
		fc_hashp->alloc = fc_DynaHashAlloc;

	if (fc_flags & HASH_SHARED_MEM)
	{
		/*
		 * ctl结构和目录为共享内存
		 * 表预分配。请注意，HASH_DIRSIZE和HASH_ALLOC最好也要设置。
		 */
		fc_hashp->hctl = fc_info->hctl;
		fc_hashp->dir = (HASHSEGMENT *) (((char *) fc_info->hctl) + sizeof(HASHHDR));
		fc_hashp->hcxt = NULL;
		fc_hashp->isshared = true;

		/* 哈希表已经存在，我们只是附加到它上面 */
		if (fc_flags & HASH_ATTACH)
		{
			/* 制作一些常用值的本地副本 */
			fc_hctl = fc_hashp->hctl;
			fc_hashp->keysize = fc_hctl->keysize;
			fc_hashp->ssize = fc_hctl->ssize;
			fc_hashp->sshift = fc_hctl->sshift;

			return fc_hashp;
		}
	}
	else
	{
		/* 设置哈希表默认值 */
		fc_hashp->hctl = NULL;
		fc_hashp->dir = NULL;
		fc_hashp->hcxt = CurrentDynaHashCxt;
		fc_hashp->isshared = false;
	}

	if (!fc_hashp->hctl)
	{
		fc_hashp->hctl = (HASHHDR *) fc_hashp->alloc(sizeof(HASHHDR));
		if (!fc_hashp->hctl)
			ereport(ERROR,
					(errcode(ERRCODE_OUT_OF_MEMORY),
					 errmsg("out of memory")));
	}

	fc_hashp->frozen = false;

	fc_hdefault(fc_hashp);

	fc_hctl = fc_hashp->hctl;

	if (fc_flags & HASH_PARTITION)
	{
		/* 对于本地哈希表进行分区没有意义 */
		Assert(fc_flags & HASH_SHARED_MEM);

		/*
		 * 分区数量最好是2的幂。同时，它必须小于INT_MAX（见init_htab()），
		 * 所以调用next_pow2的整数版本。
		 */
		Assert(fc_info->num_partitions == fc_next_pow2_int(fc_info->num_partitions));

		fc_hctl->num_partitions = fc_info->num_partitions;
	}

	if (fc_flags & HASH_SEGMENT)
	{
		fc_hctl->ssize = fc_info->ssize;
		fc_hctl->sshift = my_log2(fc_info->ssize);
		/* ssize最好是2的幂 */
		Assert(fc_hctl->ssize == (1L << fc_hctl->sshift));
	}

	/*
	 * SHM哈希表具有由调用者传递的固定目录大小.
	 */
	if (fc_flags & HASH_DIRSIZE)
	{
		fc_hctl->max_dsize = fc_info->max_dsize;
		fc_hctl->dsize = fc_info->dsize;
	}

	/* 同样记住条目大小 */
	fc_hctl->keysize = fc_info->keysize;
	fc_hctl->entrysize = fc_info->entrysize;

	/* 制作常用常量字段的本地副本 */
	fc_hashp->keysize = fc_hctl->keysize;
	fc_hashp->ssize = fc_hctl->ssize;
	fc_hashp->sshift = fc_hctl->sshift;

	/* 构建哈希目录结构 */
	if (!fc_init_htab(fc_hashp, fc_nelem))
		elog(ERROR, "failed to initialize hash table \"%s\"", fc_hashp->tabname);

	/*
	 * 对于共享哈希表，预分配请求的元素数量。
	 * 这减少了运行时共享内存条件下的问题。
	 *
	 * 对于非共享哈希表，如果请求的元素数量小于我们选择的nelem_alloc，
	 * 则预分配请求的元素数量。这避免了在调用者正确估计小表大小时浪费空间。
	 */
	if ((fc_flags & HASH_SHARED_MEM) ||
		fc_nelem < fc_hctl->nelem_alloc)
	{
		int			fc_i,
					fc_freelist_partitions,
					fc_nelem_alloc,
					fc_nelem_alloc_first;

		/*
		 * 如果哈希表被分区，则为每个自由列表提供初始分配的等份。
		 * 否则，仅使用freeList[0]。
		 */
		if (IS_PARTITIONED(fc_hashp->hctl))
			fc_freelist_partitions = NUM_FREELISTS;
		else
			fc_freelist_partitions = 1;

		fc_nelem_alloc = fc_nelem / fc_freelist_partitions;
		if (fc_nelem_alloc <= 0)
			fc_nelem_alloc = 1;

		/*
		 * 确保我们会分配所有请求的元素；如果请求不能被NUM_FREELISTS整除，
		 * excess将由freeList[0]获得。
		 */
		if (fc_nelem_alloc * fc_freelist_partitions < fc_nelem)
			fc_nelem_alloc_first =
				fc_nelem - fc_nelem_alloc * (fc_freelist_partitions - 1);
		else
			fc_nelem_alloc_first = fc_nelem_alloc;

		for (fc_i = 0; fc_i < fc_freelist_partitions; fc_i++)
		{
			int			fc_temp = (fc_i == 0) ? fc_nelem_alloc_first : fc_nelem_alloc;

			if (!fc_element_alloc(fc_hashp, fc_temp, fc_i))
				ereport(ERROR,
						(errcode(ERRCODE_OUT_OF_MEMORY),
						 errmsg("out of memory")));
		}
	}

	if (fc_flags & HASH_FIXED_SIZE)
		fc_hashp->isfixed = true;
	return fc_hashp;
}

/*
 * 设置默认HASHHDR参数。
 */
static void fc_hdefault(HTAB *fc_hashp)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;

	MemSet(fc_hctl, 0, sizeof(HASHHDR));

	fc_hctl->dsize = DEF_DIRSIZE;
	fc_hctl->nsegs = 0;

	fc_hctl->num_partitions = 0;	/* 未分区 */

	/* 表没有固定的最大大小 */
	fc_hctl->max_dsize = NO_MAX_DSIZE;

	fc_hctl->ssize = DEF_SEGSIZE;
	fc_hctl->sshift = DEF_SEGSIZE_SHIFT;

#ifdef HASH_STATISTICS
	fc_hctl->accesses = fc_hctl->collisions = 0;
#endif
}

/*
 * 根据用户指定的条目大小，选择nelem_alloc，即当我们需要更多时，
 * 向哈希表添加多少元素。
 */
static int fc_choose_nelem_alloc(Size fc_entrysize)
{
	int			fc_nelem_alloc;
	Size		fc_elementSize;
	Size		fc_allocSize;

	/* 每个元素都有一个HASHELEMENT头和用户数据。 */
	/* 注意：这最好与element_alloc()匹配 */
	fc_elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(fc_entrysize);

	/*
	 * 这里的想法是选择nelem_alloc至少为32，但向上舍入，以便
	 * 分配请求将是2的幂或刚好小于2的幂。这对共享内存中的哈希表几乎没有影响，
	 * 但是对于由palloc管理的哈希表，分配请求将被四舍五入到
	 * 最近的2的幂。 如果我们未能考虑这一点，我们将浪费
	 * 多达一半的分配空间。
	 */
	fc_allocSize = 32 * 4;			/* 假设elementSize至少为8 */
	do
	{
		fc_allocSize <<= 1;
		fc_nelem_alloc = fc_allocSize / fc_elementSize;
	} while (fc_nelem_alloc < 32);

	return fc_nelem_alloc;
}

/*
 * 计算hctl的派生字段并构建初始目录/段数组
 */
static bool fc_init_htab(HTAB *fc_hashp, long fc_nelem)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	HASHSEGMENT *fc_segp;
	int			fc_nbuckets;
	int			fc_nsegs;
	int			fc_i;

	/*
	 * 如果是分区表，初始化互斥锁
	 */
	if (IS_PARTITIONED(fc_hctl))
		for (fc_i = 0; fc_i < NUM_FREELISTS; fc_i++)
			SpinLockInit(&(fc_hctl->freeList[fc_i].mutex));

	/*
	 * 为下一个更大的2的幂数量的桶分配空间，
	 * 假设期望的最大负载因子为1。
	 */
	fc_nbuckets = fc_next_pow2_int(fc_nelem);

	/*
	 * 在分区表中，nbuckets必须至少等于
	 * num_partitions；如果不够，具有明显不同分区号的键将映射到同一个桶，
	 * 从而破坏分区独立性。 （通常nbuckets会大得多；这只是一个安全检查。）
	 */
	while (fc_nbuckets < fc_hctl->num_partitions)
		fc_nbuckets <<= 1;

	fc_hctl->max_bucket = fc_hctl->low_mask = fc_nbuckets - 1;
	fc_hctl->high_mask = (fc_nbuckets << 1) - 1;

	/*
	 * 计算所需的目录段数，向上舍入到2的幂
	 */
	fc_nsegs = (fc_nbuckets - 1) / fc_hctl->ssize + 1;
	fc_nsegs = fc_next_pow2_int(fc_nsegs);

	/*
	 * 确保目录够大。如果预分配的目录太小，程序将崩溃（调用者搞砸了）。
	 */
	if (fc_nsegs > fc_hctl->dsize)
	{
		if (!(fc_hashp->dir))
			fc_hctl->dsize = fc_nsegs;
		else
			return false;
	}

	/* 分配一个目录 */
	if (!(fc_hashp->dir))
	{
		CurrentDynaHashCxt = fc_hashp->hcxt;
		fc_hashp->dir = (HASHSEGMENT *)
			fc_hashp->alloc(fc_hctl->dsize * sizeof(HASHSEGMENT));
		if (!fc_hashp->dir)
			return false;
	}

	/* 分配初始段 */
	for (fc_segp = fc_hashp->dir; fc_hctl->nsegs < fc_nsegs; fc_hctl->nsegs++, fc_segp++)
	{
		*fc_segp = fc_seg_alloc(fc_hashp);
		if (*fc_segp == NULL)
			return false;
	}

	/* 选择一次分配的条目数量 */
	fc_hctl->nelem_alloc = fc_choose_nelem_alloc(fc_hctl->entrysize);

#ifdef HASH_DEBUG
#ifdef FDD//cppcheck
	//cppcheck，参数过多
	fprintf(stderr, "init_htab:\n%s%p\n%s%ld\n%s%ld\n%s%d\n%s%u\n%s%x\n%s%x\n%s%ld\n",
#else
	fprintf(stderr, "init_htab:\n%s%p\n%s%ld\n%s%ld\n%s%d\n%s%ld\n%s%u\n%s%x\n%s%x\n%s%ld\n",
#endif
			"TABLE POINTER   ", fc_hashp,
			"DIRECTORY SIZE  ", fc_hctl->dsize,
			"SEGMENT SIZE    ", fc_hctl->ssize,
			"SEGMENT SHIFT   ", fc_hctl->sshift,
			"MAX BUCKET      ", fc_hctl->max_bucket,
			"HIGH MASK       ", fc_hctl->high_mask,
			"LOW  MASK       ", fc_hctl->low_mask,
			"NSEGS           ", fc_hctl->nsegs);
#endif
	return true;
}

/*
 * 估计包含给定数量和给定大小条目的哈希表所需的空间。
 * 注意：这用于估计共享内存中哈希表的占用；因此不计算本地内存中的 HTAB。
 * 注意：假设所有哈希结构参数都有默认值！
 */
Size hash_estimate_size(long fc_num_entries, Size fc_entrysize)
{
	Size		fc_size;
	long		fc_nBuckets,
				fc_nSegments,
				fc_nDirEntries,
				fc_nElementAllocs,
				fc_elementSize,
				fc_elementAllocCnt;

	/* 估计所需的桶的数量 */
	fc_nBuckets = fc_next_pow2_long(fc_num_entries);
	/* nBuckets 所需的段数 */
	fc_nSegments = fc_next_pow2_long((fc_nBuckets - 1) / DEF_SEGSIZE + 1);
	/* 目录条目 */
	fc_nDirEntries = DEF_DIRSIZE;
	while (fc_nDirEntries < fc_nSegments)
		fc_nDirEntries <<= 1;		/* dir_alloc 在每次调用时将 dsize 加倍 */

	/* 固定控制信息 */
	fc_size = MAXALIGN(sizeof(HASHHDR));	/* 但不包括上述的 HTAB */
	/* 目录 */
	fc_size = add_size(fc_size, mul_size(fc_nDirEntries, sizeof(HASHSEGMENT)));
	/* segments */
	fc_size = add_size(fc_size, mul_size(fc_nSegments,
								   MAXALIGN(DEF_SEGSIZE * sizeof(HASHBUCKET))));
	/* 元素 --- 以 choose_nelem_alloc() 条目的组方式分配 */
	fc_elementAllocCnt = fc_choose_nelem_alloc(fc_entrysize);
	fc_nElementAllocs = (fc_num_entries - 1) / fc_elementAllocCnt + 1;
	fc_elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(fc_entrysize);
	fc_size = add_size(fc_size,
					mul_size(fc_nElementAllocs,
							 mul_size(fc_elementAllocCnt, fc_elementSize)));

	return fc_size;
}

/*
 * 为给定最大条目数的哈希表选择合适的目录大小。
 * 这只在共享内存中的哈希表中需要，其目录不能动态扩展。
 * 注意：假设所有哈希结构参数都有默认值！
 *
 * XXX 这最好与 init_htab() 的行为一致...
 */
long hash_select_dirsize(long fc_num_entries)
{
	long		fc_nBuckets,
				fc_nSegments,
				fc_nDirEntries;

	/* 估计所需的桶的数量 */
	fc_nBuckets = fc_next_pow2_long(fc_num_entries);
	/* nBuckets 所需的段数 */
	fc_nSegments = fc_next_pow2_long((fc_nBuckets - 1) / DEF_SEGSIZE + 1);
	/* 目录条目 */
	fc_nDirEntries = DEF_DIRSIZE;
	while (fc_nDirEntries < fc_nSegments)
		fc_nDirEntries <<= 1;		/* dir_alloc 在每次调用时将 dsize 加倍 */

	return fc_nDirEntries;
}

/*
 * 计算具有给定参数的共享内存哈希表所需的初始内存分配。
 * 我们需要为 HASHHDR 和（不可扩展的）目录留出空间。
 */
Size hash_get_shared_size(HASHCTL *fc_info, int fc_flags)
{
	Assert(fc_flags & HASH_DIRSIZE);
	Assert(fc_info->dsize == fc_info->max_dsize);
	return sizeof(HASHHDR) + fc_info->dsize * sizeof(HASHSEGMENT);
}


/********************** 销毁例程 ************************/

void hash_destroy(HTAB *fc_hashp)
{
	if (fc_hashp != NULL)
	{
		/* 分配方法必须是我们知道如何释放的 */
		Assert(fc_hashp->alloc == fc_DynaHashAlloc);
		/* 因此，这个哈希表必须有自己的上下文 */
		Assert(fc_hashp->hcxt != NULL);

		hash_stats("destroy", fc_hashp);

		/*
		 * 通过销毁哈希表的内存上下文来释放所有内容。
		 */
		MemoryContextDelete(fc_hashp->hcxt);
	}
}

void hash_stats(const char *fc_where, HTAB *fc_hashp)
{
#ifdef HASH_STATISTICS
	fprintf(stderr, "%s: this HTAB -- accesses %ld collisions %ld\n",
			fc_where, fc_hashp->hctl->accesses, fc_hashp->hctl->collisions);

	fprintf(stderr, "hash_stats: entries %ld keysize %ld maxp %u segmentcount %ld\n",
			hash_get_num_entries(fc_hashp), (long) fc_hashp->hctl->keysize,
			fc_hashp->hctl->max_bucket, fc_hashp->hctl->nsegs);
	fprintf(stderr, "%s: total accesses %ld total collisions %ld\n",
			fc_where, hash_accesses, hash_collisions);
	fprintf(stderr, "hash_stats: total expansions %ld\n",
			hash_expansions);
#endif
}

/******************************* 搜索例程 *****************************/


/*
 * get_hash_value -- 导出例程以计算键的哈希值
 *
 * 我们导出这个，因为对于分区表，调用者需要在搜索之前计算
 * 分区号（从哈希值的低位）。
 */
uint32 get_hash_value(HTAB *fc_hashp, const void *fc_keyPtr)
{
	return fc_hashp->hash(fc_keyPtr, fc_hashp->keysize);
}

/* 将哈希值转换为桶号 */
static inline uint32 fc_calc_bucket(HASHHDR *fc_hctl, uint32 fc_hash_val)
{
	uint32		fc_bucket;

	fc_bucket = fc_hash_val & fc_hctl->high_mask;
	if (fc_bucket > fc_hctl->max_bucket)
		fc_bucket = fc_bucket & fc_hctl->low_mask;

	return fc_bucket;
}

/*
 * hash_search -- 在表中查找键并执行操作
 * hash_search_with_hash_value -- 同上，键的哈希值已计算
 *
 * action 是以下之一：
 *		HASH_FIND：在表中查找键
 *		HASH_ENTER：在表中查找键，如果不存在则创建条目
 *		HASH_ENTER_NULL：同上，但如果内存不足则返回 NULL
 *		HASH_REMOVE：在表中查找键，如果存在则删除条目
 *
 * 返回值是指向找到/插入/删除的元素的指针（如果有），
 * 如果没有找到匹配，则返回 NULL。 （注意：在 REMOVE 操作的情况下，
 * 结果是一个悬空指针，不应被解引用！）
 *
 * 如果 HASH_ENTER 无法创建新条目，通常会报告一个通用的“内存不足”错误。
 * HASH_ENTER_NULL 操作也一样，只是如果内存不足会返回 NULL。 
 * 注意，HASH_ENTER_NULL 不能与默认的基于 palloc 的分配器一起使用，
 * 因为 palloc 内部会在内存不足时报告错误。
 *
 * 如果 foundPtr 不为 NULL，则如果我们在表中找到现有条目，*foundPtr 被设置为 true，
 * 否则为 false。这在 HASH_ENTER 情况下是必需的，但在其他情况下是多余的。
 *
 * 对于 hash_search_with_hash_value，hashvalue 参数必须用 get_hash_value() 计算。
 */
void * hash_search(HTAB *fc_hashp,
			const void *fc_keyPtr,
			HASHACTION fc_action,
			bool *fc_foundPtr)
{
	return hash_search_with_hash_value(fc_hashp,
									   fc_keyPtr,
									   fc_hashp->hash(fc_keyPtr, fc_hashp->keysize),
									   fc_action,
									   fc_foundPtr);
}

void * hash_search_with_hash_value(HTAB *fc_hashp,
							const void *fc_keyPtr,
							uint32 fc_hashvalue,
							HASHACTION fc_action,
							bool *fc_foundPtr)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	int			fc_freelist_idx = FREELIST_IDX(fc_hctl, fc_hashvalue);
	Size		fc_keysize;
	uint32		fc_bucket;
	long		fc_segment_num;
	long		fc_segment_ndx;
	HASHSEGMENT fc_segp;
	HASHBUCKET	fc_currBucket;
	HASHBUCKET *fc_prevBucketPtr;
	HashCompareFunc fc_match;

#ifdef HASH_STATISTICS
	hash_accesses++;
	fc_hctl->accesses++;
#endif

	/*
	 * 如果插入，则检查是否需要拆分桶。
	 *
	 * 注意：扩展表的失败并不是致命错误，这仅意味着我们
	 * 必须以比我们想要的更高的填充因子运行。然而，如果我们
	 * 使用 palloc 分配器，则在内存不足时无论如何会抛出错误，
	 * 因此我们必须在修改表之前进行此操作。
	 */
	if (fc_action == HASH_ENTER || fc_action == HASH_ENTER_NULL)
	{
		/*
		 * 如果在分区模式中运行，或如果被冻结，或如果表
		 * 是任何活动的 hash_seq_search 扫描的主题，则无法拆分。
		 */
		if (fc_hctl->freeList[0].nentries > (long) fc_hctl->max_bucket &&
			!IS_PARTITIONED(fc_hctl) && !fc_hashp->frozen &&
			!fc_has_seq_scans(fc_hashp))
			(void) fc_expand_table(fc_hashp);
	}

	/*
	 * 执行初始查找
	 */
	fc_bucket = fc_calc_bucket(fc_hctl, fc_hashvalue);

	fc_segment_num = fc_bucket >> fc_hashp->sshift;
	fc_segment_ndx = MOD(fc_bucket, fc_hashp->ssize);

	fc_segp = fc_hashp->dir[fc_segment_num];

	if (fc_segp == NULL)
		fc_hash_corrupted(fc_hashp);

	fc_prevBucketPtr = &fc_segp[fc_segment_ndx];
	fc_currBucket = *fc_prevBucketPtr;

	/*
	 * 跟随碰撞链查找匹配键
	 */
	fc_match = fc_hashp->match;		/* 在内部循环中节省一次获取 */
	fc_keysize = fc_hashp->keysize;	/* 同上 */

	while (fc_currBucket != NULL)
	{
		if (fc_currBucket->hashvalue == fc_hashvalue &&
			fc_match(ELEMENTKEY(fc_currBucket), fc_keyPtr, fc_keysize) == 0)
			break;
		fc_prevBucketPtr = &(fc_currBucket->link);
		fc_currBucket = *fc_prevBucketPtr;
#ifdef HASH_STATISTICS
		hash_collisions++;
		fc_hctl->collisions++;
#endif
	}

	if (fc_foundPtr)
		*fc_foundPtr = (bool) (fc_currBucket != NULL);

	/*
	 * 好吧，现在该怎么办？
	 */
	switch (fc_action)
	{
		case HASH_FIND:
			if (fc_currBucket != NULL)
				return (void *) ELEMENTKEY(fc_currBucket);
			return NULL;

		case HASH_REMOVE:
			if (fc_currBucket != NULL)
			{
				/* 如果分区，必须锁定以接触 nentries 和 freeList */
				if (IS_PARTITIONED(fc_hctl))
					SpinLockAcquire(&(fc_hctl->freeList[fc_freelist_idx].mutex));

				/* 从适当的 nentries 计数器中删除记录。 */
				Assert(fc_hctl->freeList[fc_freelist_idx].nentries > 0);
				fc_hctl->freeList[fc_freelist_idx].nentries--;

				/* 从哈希桶的链中删除记录。 */
				*fc_prevBucketPtr = fc_currBucket->link;

				/* 将记录添加到适当的自由列表。 */
				fc_currBucket->link = fc_hctl->freeList[fc_freelist_idx].freeList;
				fc_hctl->freeList[fc_freelist_idx].freeList = fc_currBucket;

				if (IS_PARTITIONED(fc_hctl))
					SpinLockRelease(&fc_hctl->freeList[fc_freelist_idx].mutex);

				/*
				 * 希望调用者在同步访问这个
				 * 元素，因为其他人会在下次向表中添加
				 * 内容时重用它。
				 */
				return (void *) ELEMENTKEY(fc_currBucket);
			}
			return NULL;

		case HASH_ENTER_NULL:
			/* ENTER_NULL 不适用于基于 palloc 的分配器 */
			Assert(fc_hashp->alloc != fc_DynaHashAlloc);
			/* FALL THRU */

		case HASH_ENTER:
			/* 如果找到了现有元素，则返回它，否则创建一个 */
			if (fc_currBucket != NULL)
				return (void *) ELEMENTKEY(fc_currBucket);

			/* 冻结时不允许插入 */
			if (fc_hashp->frozen)
				elog(ERROR, "cannot insert into frozen hashtable \"%s\"",
					 fc_hashp->tabname);

			fc_currBucket = get_hash_entry(fc_hashp, fc_freelist_idx);
			if (fc_currBucket == NULL)
			{
				/* 内存不足 */
				if (fc_action == HASH_ENTER_NULL)
					return NULL;
				/* 报告一个通用消息 */
				if (fc_hashp->isshared)
					ereport(ERROR,
							(errcode(ERRCODE_OUT_OF_MEMORY),
							 errmsg("out of shared memory")));
				else
					ereport(ERROR,
							(errcode(ERRCODE_OUT_OF_MEMORY),
							 errmsg("out of memory")));
#ifdef FDD//cppcheck
				return NULL;
#endif
			}

			/* 链接到 hashbucket 链中 */
			*fc_prevBucketPtr = fc_currBucket;
			fc_currBucket->link = NULL;

			/* 将键复制到记录中 */
			fc_currBucket->hashvalue = fc_hashvalue;
			fc_hashp->keycopy(ELEMENTKEY(fc_currBucket), fc_keyPtr, fc_keysize);

			/*
			 * 调用者应该在返回时填充数据字段。请勿
			 * 在此插入可能抛出错误的代码，因为这样会使表项不完整，从而破坏
			 * 调用者的数据结构。
			 */

			return (void *) ELEMENTKEY(fc_currBucket);
	}

	elog(ERROR, "unrecognized hash action code: %d", (int) fc_action);

	return NULL;				/* 保持编译器安静 */
}

/*
 * hash_update_hash_key -- 更改现有表项的哈希键
 *
 * 这相当于移除该项、创建一个新项并复制
 * 其数据，只是该项不会进入表的空闲列表。
 * 因此，即使其他进程在哈希表的其他分区中操作，这也不会遭受内存不足的失败。
 *
 * 如果成功，则返回 true；如果请求的新哈希键已存在，则返回 false。 如果指定的条目指针实际上不是
 * 表成员，则抛出错误。
 *
 * 注意：当前，对于旧哈希键和新哈希键相同的情况，没有特殊情况，这意味着我们会对此情况报告 false。
 * 这对现有用法是可取的。
 *
 * 注意：对于分区哈希表，如果新哈希键属于不同的分区，调用者必须同时持有相关
 * 分区的锁。
 */
bool hash_update_hash_key(HTAB *fc_hashp,
					 void *fc_existingEntry,
					 const void *fc_newKeyPtr)
{
	HASHELEMENT *fc_existingElement = ELEMENT_FROM_KEY(fc_existingEntry);
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	uint32		fc_newhashvalue;
	Size		fc_keysize;
	uint32		fc_bucket;
	uint32		fc_newbucket;
	long		fc_segment_num;
	long		fc_segment_ndx;
	HASHSEGMENT fc_segp;
	HASHBUCKET	fc_currBucket;
	HASHBUCKET *fc_prevBucketPtr;
	HASHBUCKET *fc_oldPrevPtr;
	HashCompareFunc fc_match;

#ifdef HASH_STATISTICS
	hash_accesses++;
	fc_hctl->accesses++;
#endif

	/* 冻结时不允许更新 */
	if (fc_hashp->frozen)
		elog(ERROR, "cannot update in frozen hashtable \"%s\"",
			 fc_hashp->tabname);

	/*
	 * 使用已保存的哈希值查找现有元素。我们需要这样做
	 * 来能够将其从哈希链中解除链接，但作为额外的好处
	 * 我们可以验证传递的 existingEntry 指针的有效性。
	 */
	fc_bucket = fc_calc_bucket(fc_hctl, fc_existingElement->hashvalue);

	fc_segment_num = fc_bucket >> fc_hashp->sshift;
	fc_segment_ndx = MOD(fc_bucket, fc_hashp->ssize);

	fc_segp = fc_hashp->dir[fc_segment_num];

	if (fc_segp == NULL)
		fc_hash_corrupted(fc_hashp);

	fc_prevBucketPtr = &fc_segp[fc_segment_ndx];
	fc_currBucket = *fc_prevBucketPtr;

	while (fc_currBucket != NULL)
	{
		if (fc_currBucket == fc_existingElement)
			break;
		fc_prevBucketPtr = &(fc_currBucket->link);
		fc_currBucket = *fc_prevBucketPtr;
	}

	if (fc_currBucket == NULL)
		elog(ERROR, "hash_update_hash_key argument is not in hashtable \"%s\"",
			 fc_hashp->tabname);

	fc_oldPrevPtr = fc_prevBucketPtr;

	/*
	 * 现在执行相当于 HASH_ENTER 操作以定位我们要放置条目的哈希
	 * 链。
	 */
	fc_newhashvalue = fc_hashp->hash(fc_newKeyPtr, fc_hashp->keysize);

	fc_newbucket = fc_calc_bucket(fc_hctl, fc_newhashvalue);

	fc_segment_num = fc_newbucket >> fc_hashp->sshift;
	fc_segment_ndx = MOD(fc_newbucket, fc_hashp->ssize);

	fc_segp = fc_hashp->dir[fc_segment_num];

	if (fc_segp == NULL)
		fc_hash_corrupted(fc_hashp);

	fc_prevBucketPtr = &fc_segp[fc_segment_ndx];
	fc_currBucket = *fc_prevBucketPtr;

	/*
	 * 跟随碰撞链查找匹配键
	 */
	fc_match = fc_hashp->match;		/* 在内部循环中节省一次获取 */
	fc_keysize = fc_hashp->keysize;	/* 同上 */

	while (fc_currBucket != NULL)
	{
		if (fc_currBucket->hashvalue == fc_newhashvalue &&
			fc_match(ELEMENTKEY(fc_currBucket), fc_newKeyPtr, fc_keysize) == 0)
			break;
		fc_prevBucketPtr = &(fc_currBucket->link);
		fc_currBucket = *fc_prevBucketPtr;
#ifdef HASH_STATISTICS
		hash_collisions++;
		fc_hctl->collisions++;
#endif
	}

	if (fc_currBucket != NULL)
		return false;			/* 与现有条目冲突 */

	fc_currBucket = fc_existingElement;

	/*
	 * 如果旧哈希值和新哈希值属于同一个桶，则无需
	 * 更改任何链链接，实际上也不应该这样，因为这种简单的
	 * 更新会在 currBucket 是最后一个元素时破坏列表。 （然而，我们
	 * 不能早些退出，因为我们需要扫描桶以检查重复键。）
	 */
	if (fc_bucket != fc_newbucket)
	{
		/* 可以从旧哈希桶链中删除记录。 */
		*fc_oldPrevPtr = fc_currBucket->link;

		/* 链接到新哈希桶链中 */
		*fc_prevBucketPtr = fc_currBucket;
		fc_currBucket->link = NULL;
	}

	/* 将新键复制到记录中 */
	fc_currBucket->hashvalue = fc_newhashvalue;
	fc_hashp->keycopy(ELEMENTKEY(fc_currBucket), fc_newKeyPtr, fc_keysize);

	/* 记录的其余部分不变 */

	return true;
}

/*
 * 如果可能的话，分配一个新的哈希表项；如果内存不足则返回 NULL。
 * （或者，如果底层空间分配器因为内存不足而抛出错误，
 * 我们将根本不返回。）
 */
static HASHBUCKET
get_hash_entry(HTAB *fc_hashp, int fc_freelist_idx)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	HASHBUCKET	fc_newElement;

	for (;;)
	{
		/* 如果分区，必须锁定以接触 nentries 和 freeList */
		if (IS_PARTITIONED(fc_hctl))
			SpinLockAcquire(&fc_hctl->freeList[fc_freelist_idx].mutex);

		/* 尝试从空闲列表获取一个条目 */
		fc_newElement = fc_hctl->freeList[fc_freelist_idx].freeList;

		if (fc_newElement != NULL)
			break;

		if (IS_PARTITIONED(fc_hctl))
			SpinLockRelease(&fc_hctl->freeList[fc_freelist_idx].mutex);

		/*
		 * 这个空闲列表中没有空闲元素。在一个分区表中，可能存在其他空闲列表
		 * 中的条目，但为了减少争用，我们更愿意首先尝试从主
		 * shmem 分配器获取另一个桶块。如果失败的话，我们 *必须* 在放弃之前
		 * 遍历所有其他的空闲列表。有多个调用者
		 * 假设他们可以分配初始请求表大小中的每个元素，或者删除一个元素保证他们
		 * 可以插入一个新元素，即使共享内存完全满了。
		 * 由于所需的元素在不同的空闲列表中而失败是不可接受的。
		 */
		if (!fc_element_alloc(fc_hashp, fc_hctl->nelem_alloc, fc_freelist_idx))
		{
			int			fc_borrow_from_idx;

			if (!IS_PARTITIONED(fc_hctl))
				return NULL;	/* 内存不足 */

			/* 尝试从另一个空闲列表借用元素 */
			fc_borrow_from_idx = fc_freelist_idx;
			for (;;)
			{
				fc_borrow_from_idx = (fc_borrow_from_idx + 1) % NUM_FREELISTS;
				if (fc_borrow_from_idx == fc_freelist_idx)
					break;		/* 检查所有空闲列表，失败 */

				SpinLockAcquire(&(fc_hctl->freeList[fc_borrow_from_idx].mutex));
				fc_newElement = fc_hctl->freeList[fc_borrow_from_idx].freeList;

				if (fc_newElement != NULL)
				{
					fc_hctl->freeList[fc_borrow_from_idx].freeList = fc_newElement->link;
					SpinLockRelease(&(fc_hctl->freeList[fc_borrow_from_idx].mutex));

					/* 小心：在其适当的空闲列表中计算新元素 */
					SpinLockAcquire(&fc_hctl->freeList[fc_freelist_idx].mutex);
					fc_hctl->freeList[fc_freelist_idx].nentries++;
					SpinLockRelease(&fc_hctl->freeList[fc_freelist_idx].mutex);

					return fc_newElement;
				}

				SpinLockRelease(&(fc_hctl->freeList[fc_borrow_from_idx].mutex));
			}

			/* 也没有可借用的元素，因此内存不足 */
			return NULL;
		}
	}

	/* 从空闲列表中移除条目，增加 nentries */
	fc_hctl->freeList[fc_freelist_idx].freeList = fc_newElement->link;
	fc_hctl->freeList[fc_freelist_idx].nentries++;

	if (IS_PARTITIONED(fc_hctl))
		SpinLockRelease(&fc_hctl->freeList[fc_freelist_idx].mutex);

	return fc_newElement;
}

/*
 * hash_get_num_entries -- 获取哈希表中的条目数量
 */
long hash_get_num_entries(HTAB *fc_hashp)
{
	int			fc_i;
	long		fc_sum = fc_hashp->hctl->freeList[0].nentries;

	/*
	 * 我们目前不 bother 获取互斥锁；只有
	 * 在你对表的所有分区持有锁时调用此函数才是合理的。
	 */
	if (IS_PARTITIONED(fc_hashp->hctl))
	{
		for (fc_i = 1; fc_i < NUM_FREELISTS; fc_i++)
			fc_sum += fc_hashp->hctl->freeList[fc_i].nentries;
	}

	return fc_sum;
}


/*
 * hash_seq_init/_search/_term
 *			顺序搜索哈希表并逐个返回所有元素，当没有更多元素时返回NULL。
 *
 * 只有在扫描在完成之前被放弃的情况下才应该调用hash_seq_term；如果hash_seq_search返回NULL，则已经完成了扫描结束的清理。
 *
 * 注意：调用者可以在继续扫描之前删除返回的元素。然而，在扫描进行时删除任何其他元素是未定义的（它可能是当前索引curIndex指向的元素！）。此外，如果在扫描进行过程中向表中添加元素，是否会被扫描访问是没有具体规定的。
 *
 * 注意：可以在不担心hash_seq_term清理的情况下使用hash_seq_init/hash_seq_search，如果在调用hash_freeze时首先锁定哈希表以防止进一步插入。
 *
 * 注意：为了在分区哈希表中使用此功能，调用者最好在整个扫描过程中对表的所有分区持有至少共享锁！我们可以处理我们自己后端的插入或删除，但*不*能处理其他的并发插入或删除。
 */
void hash_seq_init(HASH_SEQ_STATUS *fc_status, HTAB *fc_hashp)
{
	fc_status->hashp = fc_hashp;
	fc_status->curBucket = 0;
	fc_status->curEntry = NULL;
	if (!fc_hashp->frozen)
		fc_register_seq_scan(fc_hashp);
}

void * hash_seq_search(HASH_SEQ_STATUS *fc_status)
{
	HTAB	   *fc_hashp;
	HASHHDR    *fc_hctl;
	uint32		fc_max_bucket;
	long		fc_ssize;
	long		fc_segment_num;
	long		fc_segment_ndx;
	HASHSEGMENT fc_segp;
	uint32		fc_curBucket;
	HASHELEMENT *fc_curElem;

	if ((fc_curElem = fc_status->curEntry) != NULL)
	{
		/* 继续扫描curBucket... */
		fc_status->curEntry = fc_curElem->link;
		if (fc_status->curEntry == NULL)	/* 此桶的结束 */
			++fc_status->curBucket;
		return (void *) ELEMENTKEY(fc_curElem);
	}

	/*
	 * 从 curBucket 开始搜索下一个非空桶。
	 */
	fc_curBucket = fc_status->curBucket;
	fc_hashp = fc_status->hashp;
	fc_hctl = fc_hashp->hctl;
	fc_ssize = fc_hashp->ssize;
	fc_max_bucket = fc_hctl->max_bucket;

	if (fc_curBucket > fc_max_bucket)
	{
		hash_seq_term(fc_status);
		return NULL;			/* 搜索完成 */
	}

	/*
	 * 首先在表目录中找到正确的段。
	 */
	fc_segment_num = fc_curBucket >> fc_hashp->sshift;
	fc_segment_ndx = MOD(fc_curBucket, fc_ssize);

	fc_segp = fc_hashp->dir[fc_segment_num];

	/*
	 * 拿取这个桶链中的第一个项。如果链不为空，我们可以开始搜索它。
	 * 否则，我们必须向前推进以找到下一个非空桶。我们尝试优化这种情况，因为搜索一个接近空的哈希表必须多次迭代这个循环。
	 */
	while ((fc_curElem = fc_segp[fc_segment_ndx]) == NULL)
	{
		/* 空桶，推进到下一个 */
		if (++fc_curBucket > fc_max_bucket)
		{
			fc_status->curBucket = fc_curBucket;
			hash_seq_term(fc_status);
			return NULL;		/* 搜索完成 */
		}
		if (++fc_segment_ndx >= fc_ssize)
		{
			fc_segment_num++;
			fc_segment_ndx = 0;
			fc_segp = fc_hashp->dir[fc_segment_num];
		}
	}

	/* 开始扫描 curBucket... */
	fc_status->curEntry = fc_curElem->link;
	if (fc_status->curEntry == NULL)	/* 此桶的结束 */
		++fc_curBucket;
	fc_status->curBucket = fc_curBucket;
	return (void *) ELEMENTKEY(fc_curElem);
}

void hash_seq_term(HASH_SEQ_STATUS *fc_status)
{
	if (!fc_status->hashp->frozen)
		fc_deregister_seq_scan(fc_status->hashp);
}

/*
 * hash_freeze
 *			冻结哈希表以防止未来插入（删除仍然允许）
 *
 * 这样做的原因是，通过防止任何更多的桶分裂，
 * 我们不再需要担心注册 hash_seq_search 扫描，
 * 因此调用者不必小心确保在正确的时间调用 hash_seq_term。
 *
 * 允许多次调用 hash_freeze()，但您不能冻结一个有活动扫描的表
 * （因为那样 hash_seq_term 将会做错事）。
 */
void hash_freeze(HTAB *fc_hashp)
{
	if (fc_hashp->isshared)
		elog(ERROR, "cannot freeze shared hashtable \"%s\"", fc_hashp->tabname);
	if (!fc_hashp->frozen && fc_has_seq_scans(fc_hashp))
		elog(ERROR, "cannot freeze hashtable \"%s\" because it has active scans",
			 fc_hashp->tabname);
	fc_hashp->frozen = true;
}


/********************************* 工具 ************************/

/*
 * 通过添加一个哈希桶来扩展表。
 */
static bool fc_expand_table(HTAB *fc_hashp)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	HASHSEGMENT fc_old_seg,
				fc_new_seg;
	long		fc_old_bucket,
				fc_new_bucket;
	long		fc_new_segnum,
				fc_new_segndx;
	long		fc_old_segnum,
				fc_old_segndx;
	HASHBUCKET *fc_oldlink,
			   *fc_newlink;
	HASHBUCKET	fc_currElement,
				fc_nextElement;

	Assert(!IS_PARTITIONED(fc_hctl));

#ifdef HASH_STATISTICS
	hash_expansions++;
#endif

	fc_new_bucket = fc_hctl->max_bucket + 1;
	fc_new_segnum = fc_new_bucket >> fc_hashp->sshift;
	fc_new_segndx = MOD(fc_new_bucket, fc_hashp->ssize);

	if (fc_new_segnum >= fc_hctl->nsegs)
	{
		/* 如果必要，分配新段 - 如果目录已满可能会失败 */
		if (fc_new_segnum >= fc_hctl->dsize)
			if (!fc_dir_realloc(fc_hashp))
				return false;
		if (!(fc_hashp->dir[fc_new_segnum] = fc_seg_alloc(fc_hashp)))
			return false;
		fc_hctl->nsegs++;
	}

	/* 好的，我们创建了一个新桶 */
	fc_hctl->max_bucket++;

	/*
	 * *在* 更改掩码之前，找到与相同哈希值相对应的旧桶；
	 * 该桶中的值可能需要重新定位到新桶。
	 * 注意，此时 new_bucket 的确大于 low_mask，
	 * 因此我们可以跳过常规哈希掩码计算的第一步。
	 */
	fc_old_bucket = (fc_new_bucket & fc_hctl->low_mask);

	/*
	 * 如果我们跨越了 2 的幂次方，重新调整掩码。
	 */
	if ((uint32) fc_new_bucket > fc_hctl->high_mask)
	{
		fc_hctl->low_mask = fc_hctl->high_mask;
		fc_hctl->high_mask = (uint32) fc_new_bucket | fc_hctl->low_mask;
	}

	/*
	 * 将记录重新定位到新桶。注意：由于在 calc_bucket 中进行的哈希
	 * 掩码处理，当前只能有一个旧桶需要在此时分裂。
	 * 如果采用不同的方式减少哈希值，情况可能不是这样！
	 */
	fc_old_segnum = fc_old_bucket >> fc_hashp->sshift;
	fc_old_segndx = MOD(fc_old_bucket, fc_hashp->ssize);

	fc_old_seg = fc_hashp->dir[fc_old_segnum];
	fc_new_seg = fc_hashp->dir[fc_new_segnum];

	fc_oldlink = &fc_old_seg[fc_old_segndx];
	fc_newlink = &fc_new_seg[fc_new_segndx];

	for (fc_currElement = *fc_oldlink;
		 fc_currElement != NULL;
		 fc_currElement = fc_nextElement)
	{
		fc_nextElement = fc_currElement->link;
		if ((long) fc_calc_bucket(fc_hctl, fc_currElement->hashvalue) == fc_old_bucket)
		{
			*fc_oldlink = fc_currElement;
			fc_oldlink = &fc_currElement->link;
		}
		else
		{
			*fc_newlink = fc_currElement;
			fc_newlink = &fc_currElement->link;
		}
	}
	/* 不要忘记终止重建的哈希链... */
	*fc_oldlink = NULL;
	*fc_newlink = NULL;

	return true;
}


static bool fc_dir_realloc(HTAB *fc_hashp)
{
	HASHSEGMENT *fc_p;
	HASHSEGMENT *fc_old_p;
	long		fc_new_dsize;
	long		fc_old_dirsize;
	long		fc_new_dirsize;

	if (fc_hashp->hctl->max_dsize != NO_MAX_DSIZE)
		return false;

	/* 重新分配目录 */
	fc_new_dsize = fc_hashp->hctl->dsize << 1;
	fc_old_dirsize = fc_hashp->hctl->dsize * sizeof(HASHSEGMENT);
	fc_new_dirsize = fc_new_dsize * sizeof(HASHSEGMENT);

	fc_old_p = fc_hashp->dir;
	CurrentDynaHashCxt = fc_hashp->hcxt;
	fc_p = (HASHSEGMENT *) fc_hashp->alloc((Size) fc_new_dirsize);

	if (fc_p != NULL)
	{
		memcpy(fc_p, fc_old_p, fc_old_dirsize);
		MemSet(((char *) fc_p) + fc_old_dirsize, 0, fc_new_dirsize - fc_old_dirsize);
		fc_hashp->dir = fc_p;
		fc_hashp->hctl->dsize = fc_new_dsize;

		/* XXX 假设分配器是 palloc，因此我们知道如何释放 */
		Assert(fc_hashp->alloc == fc_DynaHashAlloc);
		pfree(fc_old_p);

		return true;
	}

	return false;
}


static HASHSEGMENT
fc_seg_alloc(HTAB *fc_hashp)
{
	HASHSEGMENT fc_segp;

	CurrentDynaHashCxt = fc_hashp->hcxt;
	fc_segp = (HASHSEGMENT) fc_hashp->alloc(sizeof(HASHBUCKET) * fc_hashp->ssize);

	if (!fc_segp)
		return NULL;

	MemSet(fc_segp, 0, sizeof(HASHBUCKET) * fc_hashp->ssize);

	return fc_segp;
}

/*
 * 分配一些新元素并将它们链接到指定的空闲列表中
 */
static bool fc_element_alloc(HTAB *fc_hashp, int fc_nelem, int fc_freelist_idx)
{
	HASHHDR    *fc_hctl = fc_hashp->hctl;
	Size		fc_elementSize;
	HASHELEMENT *fc_firstElement;
	HASHELEMENT *fc_tmpElement;
	HASHELEMENT *fc_prevElement;
	int			fc_i;

	if (fc_hashp->isfixed)
		return false;

	/* 每个元素都有一个HASHELEMENT头和用户数据。 */
	fc_elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(fc_hctl->entrysize);

	CurrentDynaHashCxt = fc_hashp->hcxt;
	fc_firstElement = (HASHELEMENT *) fc_hashp->alloc(fc_nelem * fc_elementSize);

	if (!fc_firstElement)
		return false;

	/* 准备将所有新条目链接到空闲列表中 */
	fc_prevElement = NULL;
	fc_tmpElement = fc_firstElement;
	for (fc_i = 0; fc_i < fc_nelem; fc_i++)
	{
		fc_tmpElement->link = fc_prevElement;
		fc_prevElement = fc_tmpElement;
		fc_tmpElement = (HASHELEMENT *) (((char *) fc_tmpElement) + fc_elementSize);
	}

	/* 如果分区了，必须锁定才能接触 freeList */
	if (IS_PARTITIONED(fc_hctl))
		SpinLockAcquire(&fc_hctl->freeList[fc_freelist_idx].mutex);

	/* 如果两个后端同时执行此操作，空闲列表可能不是空的 */
	fc_firstElement->link = fc_hctl->freeList[fc_freelist_idx].freeList;
	fc_hctl->freeList[fc_freelist_idx].freeList = fc_prevElement;

	if (IS_PARTITIONED(fc_hctl))
		SpinLockRelease(&fc_hctl->freeList[fc_freelist_idx].mutex);

	return true;
}

/* 当我们检测到哈希表损坏时进行抱怨 */
static void fc_hash_corrupted(HTAB *fc_hashp)
{
	/*
	 * 如果损坏发生在共享哈希表中，我们最好强制系统范围的重启。
	 * 否则，关闭这个后端即可。
	 */
	if (fc_hashp->isshared)
		elog(PANIC, "hash table \"%s\" corrupted", fc_hashp->tabname);
	else
		elog(FATAL, "hash table \"%s\" corrupted", fc_hashp->tabname);
}

/* 计算 num 的 ceil(log base 2) */
int my_log2(long fc_num)
{
	/*
	 * 防止过大的输入，这在 pg_ceil_log2_*() 中是无效的
	 */
	if (fc_num > LONG_MAX / 2)
		fc_num = LONG_MAX / 2;

#if SIZEOF_LONG < 8
	return pg_ceil_log2_32(num);
#else
	return pg_ceil_log2_64(fc_num);
#endif
}

/* 计算第一个 ≥ num 的 2 的幂，限于长整型能容纳的范围 */
static long fc_next_pow2_long(long fc_num)
{
	/* my_log2 的内部范围检查足够 */
	return 1L << my_log2(fc_num);
}

/* 计算第一个 ≥ num 的 2 的幂，限于整型能容纳的范围 */
static int fc_next_pow2_int(long fc_num)
{
	if (fc_num > INT_MAX / 2)
		fc_num = INT_MAX / 2;
	return 1 << my_log2(fc_num);
}


 /************************* 顺序扫描跟踪 ************************/

/*
 * 我们在这里跟踪活动的 hash_seq_search 扫描。需要此机制的原因
 * 在于，如果在扫描过程中发生桶分裂，扫描将会混淆：它可能会多次访问条目，甚至完全跳过某些条目（如果它正在过程中处理的桶刚好分裂）。因此
 * 我们希望在任何激活的扫描在被插入的表上，禁止桶分裂。这在当前使用中是相当罕见的情况，
 * 因此，仅将分裂推迟到下一个插入似乎足够。
 *
 * 根据当前函数的使用情况，只有少数扫描可能同时打开；因此，有限大小的打开扫描堆栈似乎足够，
 * 并且我们不担心线性搜索太慢。请注意，我们确实
 * 允许同一哈希表的多个扫描同时开放。
 *
 * 如果是同一后端同时进行扫描和插入，这个机制可以支持在共享
 * 哈希表中进行并发操作。否则，将会失败，但锁定原因似乎在任何情况下都不允许这种情况，因此我们不担心。
 *
 * 如果一个瞬态哈希表在没有通知我们的情况下被删除，这种安排是相当稳健的。
 * 最坏的情况是我们可能在稍后创建的另一个表中禁止分裂，正好在相同的地址。
 * 我们将在事务结束时给出警告，以防引用泄漏，因此任何导致缺乏通知的错误都应该很容易捕捉到。
 */

#define MAX_SEQ_SCANS 100

static HTAB *seq_scan_tables[MAX_SEQ_SCANS];	/* 正在扫描的表 */
static int	seq_scan_level[MAX_SEQ_SCANS];	/* 子事务嵌套级别 */
static int	num_seq_scans = 0;


/* 注册一个表作为有活动的 hash_seq_search 扫描 */
static void fc_register_seq_scan(HTAB *fc_hashp)
{
	if (num_seq_scans >= MAX_SEQ_SCANS)
		elog(ERROR, "too many active hash_seq_search scans, cannot start one on \"%s\"",
			 fc_hashp->tabname);
	seq_scan_tables[num_seq_scans] = fc_hashp;
	seq_scan_level[num_seq_scans] = GetCurrentTransactionNestLevel();
	num_seq_scans++;
}

/* 注销一个活动扫描 */
static void fc_deregister_seq_scan(HTAB *fc_hashp)
{
	int			fc_i;

	/* 向后搜索，因为它很可能位于栈顶 */
	for (fc_i = num_seq_scans - 1; fc_i >= 0; fc_i--)
	{
		if (seq_scan_tables[fc_i] == fc_hashp)
		{
			seq_scan_tables[fc_i] = seq_scan_tables[num_seq_scans - 1];
			seq_scan_level[fc_i] = seq_scan_level[num_seq_scans - 1];
			num_seq_scans--;
			return;
		}
	}
	elog(ERROR, "no hash_seq_search scan for hash table \"%s\"",
		 fc_hashp->tabname);
}

/* 检查表是否有任何活动扫描 */
static bool fc_has_seq_scans(HTAB *fc_hashp)
{
	int			fc_i;

	for (fc_i = 0; fc_i < num_seq_scans; fc_i++)
	{
		if (seq_scan_tables[fc_i] == fc_hashp)
			return true;
	}
	return false;
}

/* 在事务结束时清理任何打开的扫描 */
void AtEOXact_HashTables(bool fc_isCommit)
{
	/*
	 * 在回滚清理期间，预期会有打开的扫描；只需安静地清理它们。
	 * 在提交时有一个打开的扫描意味着有人忘记了调用 hash_seq_term()，
	 * 所以要抱怨。
	 *
	 * 注意：这里试图打印表名是很诱人的，但请避免这样做，
	 * 以免触及已被释放的内存。反正这不是面向用户的信息，
	 * 所以不必好看。
	 */
	if (fc_isCommit)
	{
		int			fc_i;

		for (fc_i = 0; fc_i < num_seq_scans; fc_i++)
		{
			elog(WARNING, "leaked hash_seq_search scan for hash table %p",
				 seq_scan_tables[fc_i]);
		}
	}
	num_seq_scans = 0;
}

/* 在子事务结束时清理任何打开的扫描 */
void AtEOSubXact_HashTables(bool fc_isCommit, int fc_nestDepth)
{
	int			fc_i;

	/*
	 * 向后搜索以方便清理。注意我们必须检查所有条目，
	 * 而不仅仅是数组末尾的那些，因为删除技巧不保持它们的顺序。
	 */
	for (fc_i = num_seq_scans - 1; fc_i >= 0; fc_i--)
	{
		if (seq_scan_level[fc_i] >= fc_nestDepth)
		{
			if (fc_isCommit)
				elog(WARNING, "leaked hash_seq_search scan for hash table %p",
					 seq_scan_tables[fc_i]);
			seq_scan_tables[fc_i] = seq_scan_tables[num_seq_scans - 1];
			seq_scan_level[fc_i] = seq_scan_level[num_seq_scans - 1];
			num_seq_scans--;
		}
	}
}
